﻿using System.Collections.Generic;
using System.Linq;

namespace AntBot
{
	public partial class FoodCollector
	{
		//private readonly Stack<FCPosition> mQueue;
		private readonly State mState;
		private FCScore mBestScore;
		private byte mCurrDepth;
		private readonly List<Move> mCurrSolution;
		private readonly List<Move> mBestSolution;
		private readonly List<Move> mHistory;
		private readonly Timer mTimer;
		private bool isCuttedTree;

		private readonly HashTable mHashTable;
		HashTable.HashEntry mHashEntry;

		private ulong mCurrentPosHash;
		public StopReasons StopReason { get; private set; }

		public bool LogBestSolutionUpdates { get; set; }

		private string mDebugTree;
		private string mCompletedDebugTree;
		public string DebugTree
		{
			get
			{
				return
					"tree (" + ExpandedNodesCount + "/" + AllNodesCount + " nodes, depth "
					+ MaxSearchDepth +"):\n"
					+ (mCompletedDebugTree == "" ? mDebugTree : mCompletedDebugTree);
			}
		}
		public int AllNodesCount { get; private set; }
		public int ExpandedNodesCount { get; private set; }

		public double CompletedTime { get; private set; }

		public byte DepthLimit { get; set; }
		public byte MaxSearchDepth { get; private set; }

		public FCScore GetSolutionScore()
		{
			return mBestScore;
		}

		public int GetSolutionSteps()
		{
			return mBestScore.Steps;
		}

		public FoodCollector(State state)
		{
			mState = state;
			//mQueue = new Stack<FCPosition>(20);

			mCurrSolution = new List<Move>(20);
			mBestSolution = new List<Move>(20);
			mHistory = new List<Move>(20);

			DepthLimit = 0;

			LogBestSolutionUpdates = false;

			mTimer = new Timer();

			mHashTable = new HashTable();
		}

		public void InitSearch()
		{
			StopReason = StopReasons.InProgress;

			mDebugTree = "";

			mCurrSolution.Clear();
			mBestSolution.Clear();

			mCurrDepth = 0;

			isCuttedTree = false;

			mBestScore = new FCScore(int.MaxValue, mState.Food.Count);
		}

		public FCPosition InitialState()
		{
			FCPosition position = new FCPosition {Depth = 0, Items = new List<FCNode>(20), Score = {Steps = 0, FoodRemains = 0}};

			if (mState == null)
				return position;

			foreach (Location food in mState.Food)
			{
				position.Items.Add(new FCNode { Steps = 0, X = food.X, Y = food.Y, IsFood = true });
				position.Score.FoodRemains++;
			}

			foreach (Location myAnt in mState.MyAnts)
				position.Items.Add(new FCNode {Steps = 0, X = myAnt.X, Y = myAnt.Y, IsFood = false});

			mCurrentPosHash = GetHashCode(position);

			return position;
		}

		private static bool IsBetterPosition(FCScore score, FCScore bestScore)
		{
			return score < bestScore;
		}

/*
		private static bool IsPotentialBetterPosition(FCScore score, FCScore bestScore)
		{
			if (IsBetterPosition(score, bestScore))
				return true;
			return score.Steps <= bestScore.Steps;
		}
*/

		private void UpdateBestSolution(FCPosition position)
		{
			if (!IsBetterPosition(position.Score, mBestScore))
				return;

			mBestScore = position.Score;
			mBestSolution.Clear();
			foreach (Move move in mCurrSolution)
				mBestSolution.Add(move);

#if LOG
			if (!LogBestSolutionUpdates)
				return;
			Logger.Log("Current best solution score: " + mBestScore);
			Logger.Log(mCurrSolution);
#endif
		}

		private void UpdateCurrentSolution(FCPosition position)
		{
			while (mCurrDepth >= position.Depth && mCurrSolution.Count > 0)
			{
				mCurrSolution.RemoveAt(mCurrSolution.Count - 1);
				mCurrDepth--;
			}

			mCurrDepth = position.Depth;
			if (mCurrDepth <= 0) return;

			Location antLoc = new Location(position.AntX, position.AntY);
			Location foodLoc = new Location(position.FoodX, position.FoodY);
			Route route = mState.Router.SearchFoodPath(antLoc, foodLoc);
			Move move = new Move(route, Move.MoveType.FoodCollection, position.TurnsBefore);

			mCurrSolution.Add(move);

#if LOG
			AddNodeToDebugTree(position);
#endif
		}

		private bool CheckTime()
		{
			if (Config.FoodCollectorMaxTime == 0)
				return true;
			if (mTimer.GetTime() > Config.FoodCollectorMaxTime)
			{
				StopReason = StopReasons.Timeout;
				return false;
			}
			return true;
		}

		//http://mindspring.narod.ru/ai/chessalg.html (5)
		private bool IsEnoughTimeForNextIteration()
		{
			if (Config.FoodCollectorMaxTime == 0)
				return true;
			if (mTimer.GetTime() > Config.FoodCollectorMaxTime / 2)
			{
				StopReason = StopReasons.Timeout;
				return false;
			}
			return true;
		}

		//Iterative deeping search
		public List<Move> Search()
		{
			mTimer.Start();

			AllNodesCount = 0;
			ExpandedNodesCount = 0;

			List<Move> currentBestSolution = null;
			mCompletedDebugTree = "";

			for (MaxSearchDepth = 1; MaxSearchDepth <= DepthLimit || DepthLimit == 0; MaxSearchDepth++)
			{
				InitSearch();
				DoSearch(InitialState(), int.MaxValue);

				if (StopReason != StopReasons.WorkComplete)
				{
					MaxSearchDepth--;
					break; //Timeout or other limitations
				}

				Logger.Log("depth: {0} finished, elapsed time: {1}", MaxSearchDepth, mTimer.GetTime());

				mCompletedDebugTree = mDebugTree;
				currentBestSolution = mBestSolution;
				
				if (!isCuttedTree)
					break; //Search finished

				if (!IsEnoughTimeForNextIteration())
					break;
			}

			CompletedTime = mTimer.GetTime();

			if (StopReason != StopReasons.WorkComplete)
				

			SaveHistory(currentBestSolution);

			return currentBestSolution;
		}

		private int DoSearch(FCPosition position, int bestValue)
		{
			UpdateCurrentSolution(position);
			UpdateBestSolution(position);

			bool canUseHash =
				mHashTable.ProbeHash(mCurrentPosHash, (byte)(MaxSearchDepth - position.Depth), out mHashEntry);

			//explicit hash hit
			if (canUseHash && mHashEntry.Depth >= (byte)(MaxSearchDepth - position.Depth))
				return mHashEntry.Value;

			if (IsGoalPosition(position))
			{
				if (position.Depth == 0)
					StopReason = StopReasons.WorkComplete;
				return Evaluate(position);
			}

			if (!CheckTime())
				return bestValue;

			List<FCMove> moves = Expand(position);
			if (StopReason != StopReasons.InProgress)
				return bestValue;

			if (canUseHash)
				SetHashMoveFirst(moves, mHashEntry.BestMoveFrom, mHashEntry.BestMoveTo);

			int value = int.MaxValue;
			int bestPosMoveFrom = 0;
			int bestPosMoveTo = 0;

			foreach (FCMove move in moves)
			{
				if (!CheckTime())
					return bestValue;

				FCUndo undo;
				bool isLegalMove;
				DoMove(ref position, move, out undo, out isLegalMove);
				if (!isLegalMove) continue;

				int approxValue = Evaluate(position);
				if (approxValue < bestValue)
					value = DoSearch(position, bestValue);

				if (StopReason != StopReasons.InProgress)
					return bestValue;

				UndoMove(ref position, move, undo);

				if (value >= bestValue) continue;
				bestValue = value;
				bestPosMoveFrom = new Location(move.Ant.X, move.Ant.Y).GetHashCode();
				bestPosMoveTo = new Location(move.Food.X, move.Food.Y).GetHashCode();
			}

			if (position.Depth == 0 && StopReason == StopReasons.InProgress)
				StopReason = StopReasons.WorkComplete;

			if (bestPosMoveFrom != 0 && bestPosMoveTo != 0)
				mHashTable.RecordHash(mCurrentPosHash, (byte)(MaxSearchDepth - position.Depth), value, bestPosMoveFrom, bestPosMoveTo);

			return bestValue;
		}

		private void SaveHistory(List<Move> solution)
		{
			mHistory.Clear();
			if (solution == null)
				return;
			
			foreach (Move move in solution.Where(move => move.Route.Path.Count > 0))
				mHistory.Add(move);
		}

		public void UndoMove(ref FCPosition position, FCMove move, FCUndo undo)
		{
			//FCPosition precessor = position;//FCPosition.Clone(position);

			//Move ant back
			position.Items.Remove(undo.EndAnt);
			position.Items.Add(undo.StartAnt);

			mCurrentPosHash = RemoveAntFromHash(mCurrentPosHash, new Location(undo.EndAnt.X, undo.EndAnt.Y));
			mCurrentPosHash = AddAntToHash(mCurrentPosHash, new Location(undo.StartAnt.X, undo.StartAnt.Y));

			//unspawn spawned ants
			foreach (FCNode node in undo.SpawnedAnts)
			{
				FCNode ant = new FCNode(node) { IsFood = false };
				position.Items.Remove(ant);
				FCNode food = new FCNode(node) { IsFood = true, Steps = 0 };
				position.Items.Add(food);

				mCurrentPosHash = RemoveAntFromHash(mCurrentPosHash, new Location(ant.X, ant.Y));
				mCurrentPosHash = AddFoodToHash(mCurrentPosHash, new Location(food.X, food.Y));
			}

			position.Depth--;
			position.Score.FoodRemains += undo.SpawnedAnts.Count;
			position.Score.Steps -= undo.EndAnt.Steps - undo.StartAnt.Steps;

			return;
		}

		public void DoMove(ref FCPosition position, FCMove move, out FCUndo undo, out bool legalMove)
		{
			AllNodesCount++;
			legalMove = true;

			//FCPosition successor = position;//FCPosition.Clone(position);

			FCNode ant = move.Ant;
			FCNode food = move.Food;

			undo = new FCUndo {SpawnedAnts = new List<FCNode>(), StartAnt = ant};

			position.Items.Remove(ant);

			position.TurnsBefore = ant.Steps;

			position.AntX = ant.X;
			position.AntY = ant.Y;
			position.FoodX = food.X;
			position.FoodY = food.Y;

			Location antLoc = new Location(ant.X, ant.Y);
			Location foodLoc = new Location(food.X, food.Y);
			Route route = mState.Router.SearchFoodPath(antLoc, foodLoc);

			//if we spawn food before last location in path, then this turn
			//degenerates to turn for that food
			if (route == null || route.Path == null ||
				IsFoodAlongPath(position, route) || !CheckAntsOnPath(position, ref route))
			{
				legalMove = false;
				return;
			}

			ant.X = route.LastLoc.X;
			ant.Y = route.LastLoc.Y;
			//if adjacent locations (Path.Count == 1) we still need 1 turn to collect food
			ant.Steps += route.Path.Count == 1 ? 1 : route.Path.Count - 1;
			position.Items.Add(ant);

			mCurrentPosHash = RemoveAntFromHash(mCurrentPosHash, antLoc);
			mCurrentPosHash = AddAntToHash(mCurrentPosHash, new Location(ant.X, ant.Y));

			undo.EndAnt = ant;
			undo.SpawnedAnts = FoodNearLocation(position, route.LastLoc);
			for (int i = 0; i < undo.SpawnedAnts.Count; i++)
			{
				FCNode item = undo.SpawnedAnts[i];
				position.Items.Remove(item);
				position.Items.Add(new FCNode { IsFood = false, Steps = ant.Steps, X = item.X, Y = item.Y });
				item.Steps = ant.Steps;
				undo.SpawnedAnts[i] = item;

				mCurrentPosHash = RemoveFoodFromHash(mCurrentPosHash, new Location(item.X, item.Y));
				mCurrentPosHash = AddAntToHash(mCurrentPosHash, new Location(item.X, item.Y));
			}

			if (position.Depth == 0 || position.Score.Steps < ant.Steps)
				position.Score.Steps = ant.Steps;
			position.Score.FoodRemains -= undo.SpawnedAnts.Count;
			position.Depth = (byte)(position.Depth + 1);
		}

		public bool CheckAntsOnPath(FCPosition position, ref Route route)
		{
			if (route == null || route.Path == null)
				return false;

			if (Config.FoodCollectorUseSimplePathFinding)
				return true;

			if (Config.FoodCollectorTurnsForCollisionCheck == 0)
				return true;

			List<Location> antsOnPath = new List<Location>();
			for (int i = 1; i < route.Path.Count && i < Config.FoodCollectorTurnsForCollisionCheck; i++)
			{
				foreach (FCNode node in position.Items.Where(node => !node.IsFood))
				{
					if (node.X == route.Path[i].X && node.Y == route.Path[i].Y)
						antsOnPath.Add(route.Path[i]);
				}
			}

			if (antsOnPath.Count == 0)
				return true;

			try
			{
				foreach (Location location in antsOnPath)
					mState.Router.SetWater(location.Col, location.Row);

				route = mState.Router.SearchFoodPath(route.FromLoc, route.ToLoc);
				if (route == null || route.Path == null || route is NoRoute)
					return false;
			}
			finally
			{
				foreach (Location location in antsOnPath)
					mState.Router.DeleteWater(location.Col, location.Row);
			}

			return true;
		}

		private List<FCNode> FoodNearLocation(FCPosition position, Location loc)
		{
			List<FCNode> food = new List<FCNode>(10);
			food.AddRange(position.Items.Where
				(item => 
					item.IsFood && 
					mState.Map.Distance2(item.X, item.Y, loc.X, loc.Y) <= Config.GameSettings.SpawnRadius2));
			return food;
		}

		private static int FarestFoodDistance(List<FCNode> foodList, List<FCNode> antList, State state)
		{
			if (foodList == null || foodList.Count == 0)
				return 0;

			int[] closestDist = new int[foodList.Count];

			int i = 0;
			foreach (FCNode food in foodList)
			{
				closestDist[i] = int.MaxValue;
				foreach (FCNode ant in antList)
				{
					int dist2 = state.Map.Distance2(ant.X, ant.Y, food.X, food.Y);
					if (dist2 < closestDist[i])
						closestDist[i] = dist2;
				}
				i++;
			}

			int dist = int.MaxValue;
			for (int j = 0; j < foodList.Count; j++)
			{
				if (dist > closestDist[j])
					dist = closestDist[j];
			}

			return dist;
		}

		//except last position
		private bool IsFoodAlongPath(FCPosition position, Route route)
		{
			return
				route.Path != null && 
				route.Path.
				Where(location => location != route.LastLoc).
				Any(location => FoodNearLocation(position, location).Count > 0);
		}

		private bool HistoryContains(FCNode ant, FCNode food)
		{
			return mHistory.Any(move => 
				move.Route.Path != null &&
				move.Route.Path.Count > 1 &&
				move.Route.Path[1] == new Location(ant.X, ant.Y) && 
				move.Route.ToLoc == new Location(food.X, food.Y));
		}

		private static void SortMoves(List<FCMove> moves)
		{
			moves.Sort(new CompareFCNodeDistance());
		}

		private static void CropMoves(List<FCMove> moves)
		{
			if (moves.Count <= Config.FOOD_COLLECTOR_MAX_BRANCH_FACTOR)
				return;

			moves.RemoveRange(Config.FOOD_COLLECTOR_MAX_BRANCH_FACTOR,
				moves.Count - Config.FOOD_COLLECTOR_MAX_BRANCH_FACTOR);
		}

		private void GenerateMoves(FCPosition position, List<FCMove> moves)
		{
			if (moves == null)
				moves = new List<FCMove>(position.Items.Count * position.Items.Count / 2);

			foreach (FCNode food in position.Items.Where(food => food.IsFood))
				foreach (FCNode ant in position.Items.Where(ant => !ant.IsFood))
				{
					if (!CheckTime()) return;

					int manhDistance = mState.Map.ManhattanDistance(new Location(ant.X, ant.Y), new Location(food.X, food.Y));

					if (HistoryContains(ant, food))
						moves.Add(new FCMove(ant, food, -1));
					else
					{
						/*int distance2 = mState.Map.Distance2(ant.X, ant.Y, food.X, food.Y);
						if (distance2 > Config.FoodCollectorSearchRadius2) continue;*/

						if (manhDistance > Config.FoodCollectorSearchRadius2)
							continue;

						moves.Add(new FCMove(ant, food, manhDistance));
						/*FCScore appScore = new FCScore(ant.Steps + manhDistance, position.Score.FoodRemains - 1);
						
						if (IsPotentialBetterPosition(appScore, mBestScore))
							moves.Add(new FCMove(ant, food, manhDistance));*/
					}
				}
		}

		private List<FCMove> Expand(FCPosition position)
		{
			List<FCMove> childMoves = 
				new List<FCMove>(Config.FOOD_COLLECTOR_MAX_BRANCH_FACTOR);

			ExpandedNodesCount++;
			if (Config.FoodCollectorMaxExpandNodes > 0 && 
				ExpandedNodesCount >= Config.FoodCollectorMaxExpandNodes)
			{
				StopReason = StopReasons.ExpandedNodesLimitHit;
				return childMoves;
			}

			GenerateMoves(position, childMoves);
			SortMoves(childMoves);
			CropMoves(childMoves);

			return childMoves;
		}

		private static void SetHashMoveFirst(List<FCMove> moves, int hashMoveFrom, int hashMoveTo)
		{
			Location antLoc = new Location(hashMoveFrom);
			Location foodLoc = new Location(hashMoveTo);

			for (int i = 0; i < moves.Count; i++)
			{
				FCMove fcMove = moves[i];
				if (fcMove.Ant.X != antLoc.X || fcMove.Ant.Y != antLoc.Y ||
				    fcMove.Food.X != foodLoc.X || fcMove.Food.Y != foodLoc.Y) continue;
				moves.RemoveAt(i);
				moves.Insert(0, fcMove);
				break;
			}
		}

		private bool IsGoalPosition(FCPosition position)
		{
			if (position.Depth >= MaxSearchDepth)
			{
				if (position.Score.FoodRemains > 0)
					isCuttedTree = true;
				return true;
			}
			return position.Score.FoodRemains == 0;
		}

		#region position functions
		//TODO		generate many test positions, solve them exactly 
		//TODO		and compare with different Evaluate functions
		public int Evaluate(FCPosition pos)
		{
			List<FCNode> foodList = new List<FCNode>((pos.Items.Where(item => item.IsFood)));
			List<FCNode> antList = new List<FCNode>((pos.Items.Where(item => !item.IsFood)));

			//int score = foodList.Count * Config.FOOD_COLLECTOR_EVAL_FOOD_COUNT_KOEF;
			int score = pos.Score.Steps * Config.FOOD_COLLECTOR_EVAL_STEPS_COUNT_KOEF;
			score += FarestFoodDistance(foodList, antList, mState) * Config.FOOD_COLLECTOR_EVAL_FAREST_FOOD_KOEF;

			return score;
		}

		public static ulong GetHashCode(FCPosition pos)
		{
			ulong hash = 0;
			foreach (FCNode item in pos.Items)
				hash ^= ((ulong)(new Location(item.X, item.Y).GetHashCode()) << (item.IsFood ? 32 : 0));

			return hash;
		}

		public static ulong AddFoodToHash(ulong hash, Location foodLoc)
		{
			return hash ^ ((ulong)foodLoc.GetHashCode() << 32);
		}

		public static ulong AddAntToHash(ulong hash, Location antLoc)
		{
			return hash ^ (ulong)(antLoc.GetHashCode());
		}

		public static ulong RemoveFoodFromHash(ulong hash, Location foodLoc)
		{
			return AddFoodToHash(hash, foodLoc);
		}

		public static ulong RemoveAntFromHash(ulong hash, Location antLoc)
		{
			return AddAntToHash(hash, antLoc);
		}
		#endregion

#if LOG
		public void AddNodeToDebugTree(FCPosition position)
		{
			Location antLoc = new Location(position.AntX, position.AntY);
			Location foodLoc = new Location(position.FoodX, position.FoodY);

			string node = "";
			for (int i = 0; i < mCurrDepth - 1; i++)
				node += " |\t";
			node += "[-]" + antLoc + "->" + foodLoc;
			node += "=" + position.Score + (IsGoalPosition(position) ? "." : "") + "\n\r";

			mDebugTree += node;
		}

		public string HashStatictics()
		{
			return mHashTable.ToString();
		}

		public ulong GetCurrentPosHashCode()
		{
			return mCurrentPosHash;
		}
#endif
	}
}